//给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 
//
// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 
//
// 
//
// 
//
// 示例 1： 
//
// 
//输入：digits = "23"
//输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
// 
//
// 示例 2： 
//
// 
//输入：digits = ""
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：digits = "2"
//输出：["a","b","c"]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= digits.length <= 4 
// digits[i] 是范围 ['2', '9'] 的一个数字。 
// 
//
// Related Topics 哈希表 字符串 回溯 👍 2778 👎 0


package com.tyrone.leetcode.editor.cn;

import java.util.*;

public class LetterCombinationsOfAPhoneNumber {
    public static void main(String[] args) {
        Solution solution = new LetterCombinationsOfAPhoneNumber().new Solution();
        System.out.println(solution.letterCombinations("23"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        Map<Integer, String> map = new HashMap<>();

        {
            map.put(2, "abc");
            map.put(3, "def");
            map.put(4, "ghi");
            map.put(5, "jkl");
            map.put(6, "mno");
            map.put(7, "pqrs");
            map.put(8, "tuv");
            map.put(9, "wxyz");
        }
        List<String> list = new ArrayList<>();
        public List<String> letterCombinations(String digits) {
            if (digits == null || digits.isEmpty()) return list;
            dfs("",0,digits);
            return list;

//            List<String> res = new ArrayList<>();
//            if (digits == null || digits.isEmpty()) return res;
//            Queue<String> queue = new LinkedList<>();
//            String s = map.get(digits.charAt(0) - '0');
//            int n = digits.length();
//            int index = 0;
//            for (int j = 0; j < s.length(); j++) {
//                queue.add(String.valueOf(s.charAt(j)));
//            }
//            while (!queue.isEmpty()) {
//                int size = queue.size();
//                for (int i = 0; i < size; i++) {
//                    String poll = queue.poll();
//                    if (index == n - 1) {
//                        res.add(poll);
//                        continue;
//                    }
//                    String curr = map.get(digits.charAt(index + 1) - '0');
//                    for (int j = 0; j < curr.length(); j++) {
//                        queue.add(poll + curr.charAt(j));
//                    }
//                }
//                index++;
//            }
//            return res;
        }

        private void dfs(String curr,Integer index,String di){
            if (index == di.length()){
                list.add(curr);
                return;
            }
            String s = map.get(di.charAt(index)-'0');
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                dfs(curr+c,index+1,di);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}